package com.lisp.algorithm.test.sort;

import java.util.Arrays;

public class QuickSort {

	public static void main(String[] args) {
		int data[] = {109, 9, 19, 8, 27, 45, 9, 10, 2, 89, 28, 43, 2, 7, 9, 190, 9, 9};
		quickSort(data, 0, data.length-1);
		System.out.println(Arrays.toString(data));
	}
	
	private static void quickSort(int data[], int start, int end) {
		if(start < end) {
			int pIndex = partition(data, start, end);
			quickSort(data, start, pIndex-1);
			quickSort(data, pIndex+1, end);
		}
	}
	
	// start < end, start inclusive, end inclusive
	private static int partition(int data[], int start, int end) {
		int chooseValue = data[end];
		int lesserIndex = start-1;
		for(int i=start; i<end; i++) {
			if(data[i] < chooseValue) {
				ArrayUtils.swap(data, i, lesserIndex + 1);
				lesserIndex++;
			}
		}
		ArrayUtils.swap(data, end, lesserIndex+1);
		return lesserIndex + 1;
	}
	
	
}
